The present invention relates to digital LAN and WAN traffic switches, particularly asynchronous transfer mode (ATM) switches.
An ATM cell switch takes cells from many sources, and routes them to many destinations. Such a switch may be hardware-based, or hardware- and software-based. The architecture can be generalized as shown in FIG. 1. Cells arrive on input ports 1 to Nin and are switched through a switch fabric 100 to various ones of output ports 1 to Nout.
A cell is a fixed size unit which constitutes a fraction of a larger communication. Cells come in on input ports, and get routed to output ports.
Sometimes, collisions take place between cells. That is, cells come in on two or more input ports that are destined for the same output port. There are two scenarios which describe the condition when two or more cells are destined for the same output port: (1) momentary contention or cell collision; and (2) sustained contention or congestion.
In either case, the collisions create the need for queueing, where one or more cells have to wait in line to be delivered to the output port.
With some architectures, even when there are no collisions, blocking can take place. Blocking occurs when a cell cannot be delivered because the delivery of other cells is taking up the resources necessary for the delivery of the blocked cell. This is often referred to as “head of line” blocking. Blocking is undesirable, since it can delay the delivery of other cells. Also, blocked cells must be queued, just like cells delayed due to collisions.
Due to these inevitable delays in delivery, a successful architecture must properly queue cells for delivery to output ports. Such queueing is also referred to as “buffering”. Buffering requires buffer control. Buffer control tells buffers when to release a cell from a queue for delivery to an output port.
Even with buffer control, it is sometimes necessary to “drop” cells. For instance, when cells come in on input ports “1” and “2”, all destined for output port “3”, it is often the situation that more cells come in than can be output from port “3”. The cells begin to be queued-up in the buffers. If this situation persists, the buffers get filled-up, and cells must be thrown away, or “dropped”. A good design minimizes the number of dropped cells.
A highly effective buffer control strategy is dynamic input buffering and output control (DIBOC). In a DIBOC architecture, a switch fabric has an input side and an output side for switching cells received at any of a plurality of input ports to any of a plurality of output ports. Cells received at the input side and destined for the output side are buffered at the input side. The output side monitors the status of the output ports, and eventually transmits grants to release the cells buffered in the input side. Buffering cells at inputs controlled by outputs has numerous advantages. First, input buffering means that cells are dropped before being transmitted across the switch fabric whenever dropping is required, reducing the traffic load on the switch fabric during congested periods. Second, output control means that the switch may be designed according to output port bandwidth limitations, improving scalability. Third, output control means that precise control algorithms may be implemented to allocate grants in a fair manner, i.e., output control allows grants to be allocated in a logical order based on considerations such as source input port, cell priority and destination output port.
Known DIBOC architectures have relied on handshaking procedures in which requests and grants are exchanged on a “per cell” basis to secure release of cells. In such handshaking procedures, the input side transmits to the output side a request for release for each cell received. Such requests typically identify a logical output queue for the cell, e.g., the cell priority level, output, etc. The output side either queues the entire requests in an request buffer, as in Hayter, U.S. Pat. No. 5,448,559, or increments a “backlog” value in a status buffer reserved for the logical output queue, as in Khacherian, application Ser. No. 08/679,360, pending the output side's issuance of,a grant to release the cell across the switching fabric to the identified output. The grants are issued on a “per cell” basis in a logical order by arbitrating among the logical output queues having at least one request pending.
Despite the significant advantages of DIBOC as an overall buffer control strategy, there is room to improve on the “per cell” handshaking procedures implemented in known DIBOC architectures. Such handshaking procedures have several weaknesses. First, a request must be transmitted to the output side for each cell even though the cell's logical output queue may already have a cell pending, resulting in the transmission of superfluous control traffic. Second, each request received by the output side must be queued even though the logical output queue with which the request is associated may already have a cell pending, or at the very least a multi-bit “backlog” value must be retained and updated for each logical output queue, imposing unnecessary status buffering requirements. Third, whenever a request does not reach the output side due to a collision or corruption during transmission, the output side develops an inaccurate view of the status of a logical output queue, which is not easily remedied. Analogous weaknesses arise in connection with the transmission of grants to the input side on a “per cell” basis. Accordingly, there is a need for a novel buffer control strategy which provides the traditional advantages of DIBOC without the side effects of “per cell” handshaking.